package com.wtgroup.demo.leetcode.q147_链表进行插入排序;

import com.wtgroup.demo.common.bean.LinkNode;
import org.junit.Test;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/16 11:02
 */
public class Q147_My {

    @Test
    public void foo() {
        int[][] inputs = {
                // {4, 2, 1, 3},
                // {-1, 5, 3, 4, 0},
                // {1},
                {4,2,1,3},
        };
        Q147_My exe = new Q147_My();
        for (int[] input : inputs) {
            LinkNode head = LinkNode.toListNode(input);
            LinkNode linkNode = exe.insertionSortList(head);
            LinkNode.print(linkNode);
            LinkNode head2 = linkNode.toListNode(input);
            LinkNode res2 = new Solution_T20210505().insertionSortList(head2);
            res2.print();
        }
    }


    /**
     * 自己实现
     */
    public LinkNode insertionSortList(LinkNode head) {
        LinkNode sortedHead = head;
        LinkNode sortedTail = head;
        while (head!=null) {
            LinkNode cur = head;
            // cur 就是本次的待排节点, 二话不说, 先把它"砍下来"放到一边. 未排序局部链表 head 后移一步.
            sortedTail.next = head.next;
            head = head.next;

            // 插入
            LinkNode preTmp = null;
            LinkNode tmp = sortedHead;
            while (tmp!=head && tmp.value <=cur.value) {preTmp = tmp; tmp=tmp.next;}
            if (preTmp==null) {
                sortedHead = cur;
            } else if (preTmp == sortedTail) {
                preTmp.next = cur;
                sortedTail = cur;
            } else {
                preTmp.next = cur;
            }
            cur.next = tmp;
        }

        return sortedHead;
    }






    // 28 ms , 18.9%
    private class Solution_T20210505 {

        public LinkNode insertionSortList(LinkNode head) {
            if (head == null) {
                return head;
            }

            LinkNode dummyHead = new LinkNode(-1, head);
            // 认为第一个节点, 插入完成
            LinkNode sortedTail = head;
            // head = head.next; // head 始终代表未排序局部链表的头 --> 改为 sortedTail.next 代替, 减少维护的变量
            LinkNode cur = null;
            while ((cur = sortedTail.next) != null) {

                // 简单考虑, 就是拿到待排节点, 从头遍历比较
                LinkNode prev = dummyHead;
                while (prev.next != sortedTail.next && prev.next.value <= cur.value) {prev = prev.next;}
                if (prev.next == sortedTail.next) {
                    // cur 应该成为新的 sortedTail
                    sortedTail.next = cur;
                    sortedTail = cur;
                } else {
                    sortedTail.next = cur.next;
                    cur.next = prev.next;
                    prev.next = cur;
                }
            }

            return dummyHead.next;
        }

    }









}
